"""
870. 优势洗牌
中等
相关标签
相关企业
给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的 任意 排列，使其相对于 nums2 的优势最大化。



示例 1：

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]
示例 2：

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]


提示：

1 <= nums1.length <= 105
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 109
"""


class Solution(object):
    def advantageCount(self, nums1, nums2):
        nums1.sort()

        n = len(nums1)
        ids = sorted(range(n), key=lambda i: nums2[i])

        ans = [0] * n
        left, right = 0, n - 1
        for x in nums1:
            if x > nums2[ids[left]]:
                ans[ids[left]] = x  # 用下等马比下等马
                left += 1
            else:
                ans[ids[right]] = x  # 用下等马比上等马
                right -= 1
        return ans


    def advantageCount_err1(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        错误，注意原本的nums顺序不能改变
        """
        nums1.sort()
        nums2.sort()
        smallList = [] #存储nums1较小的数，最后添加到largeList中
        dp = [] #结果
        i = 0
        j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] > nums2[j]:
                dp.append(nums1[i])
                i += 1
                j += 1
            else:
                smallList.append(nums1[i])
                i += 1
        dp.extend(smallList)
        return dp